package com.wangwan.suanfa;

public class KnapsackOptimized {

    public static void main(String[] args) {
        // 物品的重量和价值
        int[] weights = {5,3,2,1}; // 每个物品的重量
        int[] values = {4,4,3,1};  // 每个物品的价值
        int capacity = 6; // 背包的容量

        // 调用优化后的解决方法
        int maxValue = knapsack(weights, values, capacity);

        System.out.println("背包的最大价值是：" + maxValue);
    }

    /**
     * 使用一维数组解决 0/1 背包问题
     *
     * @param weights  每个物品的重量数组
     * @param values   每个物品的价值数组
     * @param capacity 背包容量
     * @return 背包能装下的最大价值
     */
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length; // 物品数量

        // 使用一维数组 dp
        // dp[j] 表示背包容量为 j 时的最大价值
        int[] dp = new int[capacity + 1];

        // 遍历每个物品
        for (int i = 0; i < n; i++) {
            // 从后向前遍历背包容量，确保每个物品只能使用一次
            for (int j = capacity; j >= weights[i]; j--) {
                // 更新 dp[j] 的值
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }

        // 返回 dp 数组中容量为 capacity 时的最大价值
        return dp[capacity];
    }
}
